package com.lun.medium;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class FindACorrespondingNodeOfABinaryTreeInACloneOfThatTree {
   public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
       
	   LinkedList<TreeNode> stack = new LinkedList<>();
	   stack.push(cloned);
	   while(!stack.isEmpty()) {
		   TreeNode node = stack.pop();
		   
		   if(node.val == target.val)
			   return node;
		   
		   if(node.left != null)
			   stack.push(node.left);
		   
		   if(node.right != null)
			   stack.push(node.right);
		   
	   }
	   return null;
   }
}
